home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / FROMUTS / XLISP1 / lisp / PROLOG < prev    next >
Lisp/Scheme  |  1990-02-23  |  4KB  |  105 lines
  1.  
  2. ;; The following is a tiny Prolog interpreter in MacLisp
  3. ;; written by Ken Kahn and modified for XLISP by David Betz.
  4. ;; It was inspired by other tiny Lisp-based Prologs of
  5. ;; Par Emanuelson and Martin Nilsson.
  6. ;; There are no side-effects anywhere in the implementation.
  7. ;; Though it is VERY slow of course.
  8.  
  9. (defun prolog (database &aux goal)
  10.        (do () ((not (progn (princ "Query?") (setq goal (read)))))
  11.               (prove (list (rename-variables goal '(0)))
  12.                      '((bottom-of-environment))
  13.                      database
  14.                      1)))
  15.  
  16. ;; prove - proves the conjunction of the list-of-goals
  17. ;;         in the current environment
  18.  
  19. (defun prove (list-of-goals environment database level)
  20.       (cond ((null list-of-goals) ;; succeeded since there are no goals
  21.              (print-bindings environment environment)
  22.              (not (y-or-n-p "More?")))
  23.             (t (try-each database database
  24.                          (cdr list-of-goals) (car list-of-goals)
  25.                          environment level))))
  26.  
  27. (defun try-each (database-left database goals-left goal environment level
  28.                  &aux assertion new-enviroment)
  29.        (cond ((null database-left) nil) ;; fail since nothing left in database
  30.              (t (setq assertion
  31.                       (rename-variables (car database-left)
  32.                                         (list level)))
  33.                 (setq new-environment
  34.                       (unify goal (car assertion) environment))
  35.                 (cond ((null new-environment) ;; failed to unify
  36.                        (try-each (cdr database-left) database
  37.                                  goals-left goal
  38.                                  environment level))
  39.                       ((prove (append (cdr assertion) goals-left)
  40.                               new-environment
  41.                               database
  42.                               (+ 1 level)))
  43.                       (t (try-each (cdr database-left) database
  44.                                    goals-left goal
  45.                                    environment level))))))
  46.  
  47. (defun unify (x y environment &aux new-environment)
  48.        (setq x (value x environment))
  49.        (setq y (value y environment))
  50.        (cond ((variable-p x) (cons (list x y) environment))
  51.              ((variable-p y) (cons (list y x) environment))
  52.              ((or (atom x) (atom y))
  53.                   (cond ((equal x y) environment)
  54.                         (t nil)))
  55.              (t (setq new-environment (unify (car x) (car y) environment))
  56.                 (cond (new-environment (unify (cdr x) (cdr y) new-environment))
  57.                       (t nil)))))
  58.  
  59. (defun value (x environment &aux binding)
  60.        (cond ((variable-p x)
  61.               (setq binding (assoc x environment :test #'equal))
  62.               (cond ((null binding) x)
  63.                     (t (value (cadr binding) environment))))
  64.              (t x)))
  65.  
  66. (defun variable-p (x)
  67.        (and x (listp x) (eq (car x) '?)))
  68.  
  69. (defun rename-variables (term list-of-level)
  70.        (cond ((variable-p term) (append term list-of-level))
  71.              ((atom term) term)
  72.              (t (cons (rename-variables (car term) list-of-level)
  73.                       (rename-variables (cdr term) list-of-level)))))
  74.  
  75. (defun print-bindings (environment-left environment)
  76.        (cond ((cdr environment-left)
  77.               (cond ((= 0 (nth 2 (caar environment-left)))
  78.                      (prin1 (cadr (caar environment-left)))
  79.                      (princ " = ")
  80.                      (print (value (caar environment-left) environment))))
  81.               (print-bindings (cdr environment-left) environment))))
  82.  
  83. ;; a sample database:
  84. (setq db '(((father madelyn ernest))
  85.            ((mother madelyn virginia))
  86.            ((father david arnold))
  87.            ((mother david pauline))
  88.            ((father rachel david))
  89.            ((mother rachel madelyn))
  90.            ((grandparent (? grandparent) (? grandchild))
  91.             (parent (? grandparent) (? parent))
  92.             (parent (? parent) (? grandchild)))
  93.            ((parent (? parent) (? child))
  94.             (mother (? parent) (? child)))
  95.            ((parent (? parent) (? child))
  96.             (father (? parent) (? child)))))
  97.  
  98. ;; the following are utilities
  99. (defun y-or-n-p (prompt)
  100.        (princ prompt)
  101.        (eq (read) 'y))
  102.  
  103. ;; start things going
  104. (prolog db)
  105.